sack algorithm
guni や DSU on Tree とも呼ばれるアルゴリズムです．
用途
任意の頂点について，その部分木に含まれている頂点の列挙やカウント等のクエリを$ \mathrm{amortized}\ \Theta(N\log N)で処理することが出来ます．
例$ 1： 全ての部分木について部分木に含まれる色ごとの数を数えよ．
例$ 2：全ての部分木について部分木の根から距離$ L以上$ R以下にある頂点のラベルの最小値を求めよ．
計算量
$ \mathrm{amortized}\ \Theta(N\log N)
実装
色のカウントをするコード例
code:cpp
std::vector<int> cnt(n, 0);
// keep := 結果を維持して戻るか？
auto dfs = &(auto && dfs, int v, int par, bool keep) -> void { int heavy = -1;
if(e == par) continue;
if(heavy == -1 or sze > szheavy) heavy = e; }
for(auto e: gv) if(e != par and e != heavy) dfs(dfs, e, v, false); if(heavy != -1) {
// 一番重い子の結果は維持させる．
dfs(dfs, heavy, v, true);
}
// 頂点 v を追加
if(e == par or e == heavy) continue;
// heavy 以外の子については，舐めて調べる．
for(int i = euler_tour_starte; i < euler_tour_ende; i++) { }
}
// この時点で cnt は v の部分木についての結果を保存している．
// 維持して戻らない場合は全て削除しておく．
if(!keep) {
for(int i = euler_tour_startv; i < euler_tour_endv; i++) { }
}
};
dfs(dfs, root, -1, false);
解説
基本は分割統治法です．
ある頂点$ vを根とするような部分木を考えます，この根からなる部分木はさらに子を根とする部分木から構成されています．
この子を根とする部分木についての結果（ここが大きくなるため問題）を再利用することで$ vの部分木について問題を解きたい，というのが sack algorithm の主題です．
再利用とかを考えずに愚直にやる（全頂点を見る）と$ O(N)かかり，全体で$ O(N^2)かかってしまいます．
そこで子の部分木の結果を維持することでオーダーを落とすことを考えます．
例えば色のカウントではカウンタ配列をひとつだけ用意してそれを使いまわすことで空間量は$ O(N)に落とせます．
ある子の部分木について解けているならば，カウンタをリセットせずに新たにそれ以外の子の部分木を追加すれば$ vの部分木全体の結果が得られます．
肝心なのはどの子の部分木の結果を使いまわすかです，直感的には頂点数が最大の子を選べば良さそうという気持ちになります．
つまり，頂点数が最大の子についてまず解き，その結果を維持したまま親（子の親なので自分）に戻り，他の子の部分木については全頂点走査するというアルゴリズムになります．
親に戻る際，自身が親にとって頂点数が最大の子でない場合は，結果を白紙にしておく必要があります．
実は，これだけで償却$ O(N\log N)になっていることがわかります．
証明
ある頂点の子の部分木が最大のものへ向かう辺を heavy-edge，それ以外の子へ向かう辺を light-edge と呼ぶことにします．
ある頂点$ uについてこれが何回調べられるかを考えます．
これは$ {\rm path}(0, u)上に light-edge が何回あるか？と同値でこれは light-edge を渡るたびに頂点数が半分になるので$ O(\log N)になることがわかります．
よって全体で$ O(N\log N)です．
実装について
はじめに Euler-Tour を構築しておくと部分木を舐める等の操作が楽に書けるのでおすすめです．
https://gyazo.com/4dc450eb94de5f239f1177ca64ab7223
応用
部分木の根からの距離ごとに調べたい状況では，陽に解こうとすると部分木の根からの距離をいちいち計算する必要があり sack algorithm を適用出来ません．
そこで木全体の根からの距離を用いることで部分木の根$ \mathrm{root}から部分木の頂点$ vまでの距離を$ \mathrm{dist}(v) - \mathrm{dist(root)}と表せることを利用します．
そうすると，部分木の根からの距離という情報を持たずに木全体の根からの距離ごとに調べることで処理することが可能になります．
例題
根が$ 0の木が与えられて，各頂点には文字が割り当てられている．
頂点$ 0からの深さが$ hであり，かつ部分木$ vに含まれるような頂点にかかれている文字を並び替えることで回分にできるか？というクエリをたくさん解け，という問題．
まず，並び替えて回分にできるというのは奇数個ある文字が一つ以下しか無いということ．
ということで各部分木について深さ$ hの頂点に書かれた文字がそれぞれいくつあるか？を数えたい．
sack で解ける！